package 力扣._00周赛._116双周赛.问题3;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Solution2 {
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        //装满背包0/1的最多物品
        int[] dp = new int[target + 1]; //最大物品
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums.get(i); j--) {
                dp[j] = Math.max(dp[j], dp[j - nums.get(i)] + 1);
            }
        }

        //再判断下背包能装的最大价值
        int[] dp2 = new int[target + 1]; //最大物品
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums.get(i); j--) {
                dp2[j] = Math.max(dp2[j], dp2[j - nums.get(i)] + nums.get(i));
            }
        }
        System.out.println(Arrays.toString(dp));
        System.out.println(Arrays.toString(dp2));
        if (dp2[target] == target)
            return dp[target];
        return -1;
//

    }

    public static void main(String[] args) {
        List<Integer> nums = new LinkedList<>();
        nums.add(3);
        nums.add(13);
        nums.add(4);
        nums.add(2);
        nums.add(6);
        nums.add(5);
        int i = new Solution2().lengthOfLongestSubsequence(nums, 24);
    }
}
